package org.czl.leetcode4;

public class l3045 {
    public static void main(String[] args) {
        System.out.println(countPrefixSuffixPairs(new String[]{"pa","papa"}));
    }
    static int MAXI = 500050;
    static int[][] tree = new int[MAXI][26];
    static int[] end = new int[MAXI];
    static int cnt = 0;
    public static long countPrefixSuffixPairs(String[] words){
        long ans = 0;
        for(String s : words){
            int n = s.length();
            int[] z = new int[n];
            z[0] = n;
            for(int i = 1, c = 1, r = 1; i < n; i++){
                int len = i < r ? Math.min(z[i - c], r - i) : 0;
                while(i + len < n && s.charAt(len) == s.charAt(len + i)){
                    len++;
                }
                if(i + len > r){
                    r = i + len;
                    c = i;
                }
                z[i] = len;
            }
            int cur = 0;
            for(int i = 0; i < n; i++){
                int index = s.charAt(i) - 'a';
                if(tree[cur][index] == 0){
                    tree[cur][index] = ++cnt;
                }
                cur = tree[cur][index];
                if(i + 1 == z[n - 1 - i]){
                    ans += end[cur];
                }
            }
            end[cur]++;
        }
        return ans;
    }
}
